π§· λμ κ³νλ² (DP)
볡μ‘ν λ¬Έμ λ₯Ό κ°λ¨ν μ¬λ¬ κ°μ λ¬Έμ λ‘ λλ νΈλ λ°©λ²μΌλ‘, ν° μλ―Έμμ λΆν μ 볡과 κ°μ μ κ·Ό λ°©μμ μλ―Ένλ€.
ν κ°μ§ λ¬Έμ μ λν΄, λ¨ ν λ²λ§ νλλ‘ λ§λ€μ΄μ£Όλ μκ³ λ¦¬μ¦μΌλ‘, λμΌν μ°μ°μ λ°λ³΅νμ§ μλλ€.
-
μ€ν μκ°μ μ€μ΄κΈ° μν΄ λ§μ΄ μ΄μ©λλ μκ³ λ¦¬μ¦ (μ΅μ ν μκ³ λ¦¬μ¦)
-
ν¨μ¨μ± ν μ€νΈκ° μλ κ²½μ°, DPλ μ΄μ§ νμμ λ§μ΄ μ¬μ©νλ€κ³ λ€ νλ€...
-
-
Optimal Substructureμμ ν¨κ³Όλ₯Ό λ°ννλ€.
-
Optimal Substructure: λ΅μ ꡬνκΈ° μν΄ μ΄λ―Έ νλ λμΌν μ°μ°μ λ°λ³΅νλ ꡬ쑰λ‘, μ΅μ ν λ¬Έμ μ λͺ¨λ νμ μ루μ μ μ΅μ μ μ루μ μ΄λ€. (Principle of Optimality)
-
λΆν μ 볡과 DPμ μ°¨μ΄μ ? : λ¬Έμ λ₯Ό λλλ λ°©μμ μμ΄ μ°¨μ΄κ° μλ€. λμ κ³νλ²μμ, μ΄λ€ λΆλΆ λ¬Έμ λ λ κ° μ΄μμ λ¬Έμ λ₯Ό νΈλ λ° μ¬μ©λ μ μμ΄ μ΄ λ¬Έμ μ λ΅μ μ¬λ¬ λ² κ³μ°νμ§ μκ³ ν λ²λ§ κ³μ°ν ν κ²°κ³Όλ₯Ό μ¬μ¬μ©νλ λ°©μμ μ·¨νλ€.
πͺ 쑰건
- μμ λ¬Έμ μμ λ°λ³΅μ΄ λ°μ
- κ°μ λ¬Έμ λ νμ κ°μ μ λ΅
μ λ κ°μ§ 쑰건μ μΆ©μ‘±νλ€λ©΄, λμ κ³νλ²μ μ¬μ©ν΄ λ¬Έμ λ₯Ό ν μ μλ€. κ·Έλ¦¬κ³ ν λ² κ³μ°ν κ²°κ³Όλ₯Ό μ μ₯νκΈ° μν΄ Memoizationμ μ¬μ©νλ€.
Memoization : ν λ² κ³μ°ν λ¬Έμ λ λ€μ κ³μ°νμ§ μλλ‘ μ μ₯ν΄λκ³ μ¬μ¬μ©νλ λ°©μ
πͺ μμ
κ°μ₯ μ λͺ ν μ μ€ νλλ μ΄ν κ³μ(binomial coefficient)μ κ³μ°μ΄λ€. μ΄ν κ³μλ nκ°μ μλ‘ λ€λ₯Έ μμ μ€ rκ°μ μμλ₯Ό μμμμ΄ κ³¨λΌλ΄λ λ°©λ²μ μλ₯Ό λνλΈλ€.
- κ·Έλ¦¬κ³ μ΄ μ νμμ μ¬κ· νΈμΆμ μ΄μ©νμ¬ κ΅¬ννλ©΄ μλμ κ°λ€.
int bino(int n, int r) {
if (r == 0 || n == r) return 1;
return bino(n - 1, r - 1) + bino(n - 1, r);
}
- μ¬κ· νΈμΆμ μννλ κ³Όμ μμ, λμΌν μ°μ°μ΄ μ€λ³΅μ μΌλ‘ νΈμΆλλ€. κ·Έλ¦¬κ³ μ΄λ¬ν μ€λ³΅ κ³μ°μ nμ΄ μ¦κ°ν λλ§λ€ κΈ°νκΈμμ μΌλ‘ μ°μ°λμ΄ μ¦κ°νλλ‘ λ§λ λ€.
-
λ°λΌμ, κ° n,r μ‘°ν©μ λν΄ λ΅μ μ μ₯νλ λ°°μ΄μ λ§λ€μ΄, κ° μ λ ₯μ λν λ°ν κ°μ μ μ₯νλλ‘ λ³κ²½νλ€.
- μ΄λ―Έ μ μ₯λ κ°μ΄ μλ€λ©΄ μ΄λ₯Ό μ¬μ¬μ©νκ³ , κ·Έλ μ§ μλ€λ©΄ μ§μ κ³μ°ν ν λ°°μ΄μ κ°μ μ μ₯νλ€.
- μ¦, Memoizationμ μ¬μ©ν΄ μ΅μ νλ₯Ό μννλ€.
// -1λ‘ μ΄κΈ°ν
int[][] cache = new int[30][30];
int bino2(int n, int r) {
if (r == 0 || n == r) return 1;
if (cache[n][r] != -1) return cache[n][r];
return cache[n][r] = bino2(n - 1, r - 1) + bino2(n - 1, r);
}
πͺ ꡬν λ°©μ
λμ κ³νλ²μ ꡬννλ λ°©μμ μμ΄ 2κ°μ§κ° κ°λ₯νλ€.
-
Bottom-up: μμ λ¬Έμ λ€λΆν° ν΄κ²°νλ©΄μ μ 체 λ΅μ ꡬνλ λ°©μ
- νν λ°λ³΅λ¬Έμ μ¬μ©ν΄ ꡬννκ³ , μ¬κ· νΈμΆμ μ¬μ©νμ§ μμ μκ°κ³Ό λ©λͺ¨λ¦¬ μ¬μ©λμ μ€μΌ μ μλ€λ μ₯μ μ΄ μλ€.
-
Top-down: κ°μ₯ ν° λ¬Έμ λ₯Ό λ°©λ¬Έ ν μμ λ¬Έμ λ₯Ό νΈμΆν΄ λ΅μ ꡬνλ λ°©μ
- νν μ¬κ· νΈμΆμ μ¬μ©ν΄ ꡬννκ³ , μ νμμ μ§κ΄μ μΌλ‘ μ΄ν΄νκΈ° μ½λ€λ μ₯μ μ΄ μλ€.
π μ°Έκ³
- Tech Interview for developer
- Top-down(νλ€μ΄) vs Bottom-up(λ°ν μ )
- [νλ‘κ·Έλλ° λνμμ λ°°μ°λ μκ³ λ¦¬μ¦ λ¬Έμ ν΄κ²° μ λ΅] κ΅¬μ’ λ§